{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Jump Game VII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canReach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #跳跃游戏 VII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0 </strong>开始的二进制字符串 <code>s</code> 和两个整数 <code>minJump</code> 和 <code>maxJump</code> 。一开始，你在下标 <code>0</code> 处，且该位置的值一定为 <code>'0'</code> 。当同时满足如下条件时，你可以从下标 <code>i</code> 移动到下标 <code>j</code> 处：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>i + minJump <= j <= min(i + maxJump, s.length - 1)</code> 且</li>\n",
    "\t<li><code>s[j] == '0'</code>.</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果你可以到达 <code>s</code> 的下标<i> </i><code>s.length - 1</code> 处，请你返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"<strong>0</strong>11<strong>0</strong>1<strong>0</strong>\", minJump = 2, maxJump = 3\n",
    "<b>输出：</b>true\n",
    "<strong>解释：</strong>\n",
    "第一步，从下标 0 移动到下标 3 。\n",
    "第二步，从下标 3 移动到下标 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"01101110\", minJump = 2, maxJump = 3\n",
    "<b>输出：</b>false\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= s.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 要么是 <code>'0'</code> ，要么是 <code>'1'</code></li>\n",
    "\t<li><code>s[0] == '0'</code></li>\n",
    "\t<li><code>1 <= minJump <= maxJump < s.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jump-game-vii](https://leetcode.cn/problems/jump-game-vii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jump-game-vii](https://leetcode.cn/problems/jump-game-vii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"011010\"\\n2\\n3', '\"01101110\"\\n2\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        que = [start]\n",
    "\n",
    "        while que:\n",
    "            node = que.pop(0)\n",
    "            if arr[node] == 0:\n",
    "                return True\n",
    "            if arr[node] < 0:\n",
    "                continue\n",
    "            for i in [node + arr[node], node - arr[node]]:\n",
    "                if 0 <= i < n:\n",
    "                    que.append(i)\n",
    "                \n",
    "            arr[node] = -arr[node]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        d = dict()\n",
    "        def reach(arr, start):\n",
    "            if start >= len(arr) or start < 0 or d.get(start, None):\n",
    "                return False\n",
    "            if arr[start] == 0:\n",
    "                return True\n",
    "            d[start] = 1\n",
    "            res_left = reach(arr, start-arr[start])\n",
    "            res_right = reach(arr, start+arr[start])\n",
    "            \n",
    "            return res_left or res_right\n",
    "\n",
    "        return reach(arr, start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        N =len(arr)\n",
    "        Q = deque([(start)])\n",
    "        seen = set([(start)])\n",
    "        while Q:\n",
    "            idx = Q.popleft()\n",
    "            if arr[idx] == 0:\n",
    "                return True\n",
    "            for nei in [idx + arr[idx], idx-arr[idx]]:\n",
    "                if 0<=nei<N and nei not in seen:\n",
    "                    seen.add(nei)\n",
    "                    Q.append(nei)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        q = deque([start])\n",
    "        vis = [False] * len(arr)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            vis[cur] = True\n",
    "            if arr[cur] == 0: return True\n",
    "            if cur - arr[cur] >= 0 and not vis[cur - arr[cur]]: \n",
    "                vis[cur - arr[cur]] = True\n",
    "                q.append(cur - arr[cur])\n",
    "            if cur + arr[cur] < len(arr) and not vis[cur + arr[cur]]:\n",
    "                vis[cur + arr[cur]] = True \n",
    "                q.append(cur + arr[cur])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        from queue import LifoQueue\n",
    "\n",
    "        length = len(arr)\n",
    "        stack = LifoQueue()\n",
    "        stack.put(start)\n",
    "        arrived = [False for _ in range(length)]\n",
    "        while not stack.empty():\n",
    "            idx = stack.get()\n",
    "            if arr[idx] == 0:\n",
    "                return True\n",
    "            if arrived[idx]:\n",
    "                return False\n",
    "\n",
    "            left, right = idx - arr[idx], idx + arr[idx]\n",
    "            if left >= 0 and not arrived[left]:\n",
    "                stack.put(left)\n",
    "            if right < length and not arrived[right]:\n",
    "                stack.put(right)\n",
    "            arrived[idx] = True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if arr[start] == 0: return True\n",
    "        if 0 not in arr: return False\n",
    "        n = len(arr)\n",
    "\n",
    "        q = deque([start])\n",
    "        vis = [False] * n\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            x = arr[i]\n",
    "            vis[i] = True\n",
    "            if x == 0: return True\n",
    "            if i-x >= 0 and not vis[i-x]: q.append(i-x)\n",
    "            if i+x < n and not vis[i+x]: q.append(i+x)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        if arr[start] == 0:\n",
    "            return True\n",
    "        used = {start}\n",
    "        q = collections.deque([start])\n",
    "        while len(q) > 0:\n",
    "            u = q.popleft()\n",
    "            for v in [u + arr[u], u - arr[u]]:\n",
    "                if 0 <= v < n and v not in used:\n",
    "                    if arr[v] == 0:\n",
    "                        return True\n",
    "                    q.append(v)\n",
    "                    used.add(v)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        from collections import deque\n",
    "        n=len(arr)\n",
    "        quene=deque()\n",
    "        quene.append(start)\n",
    "        check=set(range(n))\n",
    "        check.remove(start)\n",
    "        while quene:\n",
    "            cur=quene.popleft()\n",
    "            if arr[cur]==0:\n",
    "                return True\n",
    "            a,b=cur+arr[cur],cur-arr[cur]\n",
    "            if 0<=a<n and a in check:\n",
    "                check.remove(a)\n",
    "                quene.append(a)\n",
    "            if 0<=b<n and b in check:\n",
    "                check.remove(b)\n",
    "                quene.append(b)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if arr[start]==0:\n",
    "            return True\n",
    "        n=len(arr)\n",
    "        visited=[[False]*2 for _ in range(n)]   #visited[i][0]:从左向右移动到达下标i,visited[i][1]:从右向左移动到达下标i\n",
    "        q=deque([(start+arr[start],0),(start-arr[start],1)])\n",
    "        while q:\n",
    "            pos,dir=q.popleft()\n",
    "            if pos<0 or pos>=n or visited[pos][dir]:\n",
    "                continue\n",
    "            if arr[pos]==0:\n",
    "                return True\n",
    "            visited[pos][dir]=True\n",
    "            q.append((pos+arr[pos],0))\n",
    "            q.append((pos-arr[pos],1))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if arr[start] == 0:\n",
    "            return True\n",
    "        arr_status = {index: False for index in range(len(arr))}\n",
    "        q = queue.Queue()\n",
    "        q.put(start)\n",
    "        arr_status[start] = True\n",
    "        while q.qsize():\n",
    "            for _ in range(q.qsize()):\n",
    "                for index in self.reach(arr, q.get()):\n",
    "                    if arr[index] == 0:\n",
    "                        return True\n",
    "                    if not arr_status[index]:\n",
    "                        q.put(index)\n",
    "                        arr_status[index] = True\n",
    "            # print(arr_status)\n",
    "        return False\n",
    "\n",
    "    def reach(self, arr: List[int], start: int):\n",
    "        ret = []\n",
    "        left = start - arr[start]\n",
    "        right = start + arr[start]\n",
    "        if left >= 0:\n",
    "            ret.append(left)\n",
    "        if right <= len(arr) - 1:\n",
    "            ret.append(right)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        next = [[] for _ in arr]\n",
    "        for i, n in enumerate(arr):\n",
    "            if 0 <= i-n:\n",
    "                next[i].append(i-n)\n",
    "            if i+n < len(arr):\n",
    "                next[i].append(i+n)\n",
    "        nodes = collections.deque()\n",
    "        nodes.append(start)\n",
    "        visited = [False for p in arr]\n",
    "        while nodes:\n",
    "            cn = nodes.popleft()\n",
    "            if arr[cn] == 0:\n",
    "                return True\n",
    "            visited[cn] = True\n",
    "            for nn in next[cn]:\n",
    "                if not visited[nn]:\n",
    "                    nodes.append(nn)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        routes = [[] for i in range(len(arr))]\n",
    "        for i in range(len(arr)):\n",
    "            l = i - arr[i]\n",
    "            if l >= 0:\n",
    "                routes[i].append(l)\n",
    "            r = i + arr[i]\n",
    "            if r < len(arr):\n",
    "                routes[i].append(r)\n",
    "        bfs = collections.deque([start])\n",
    "        visit = [False for i in range(len(arr))]\n",
    "        visit[start] = True\n",
    "        while len(bfs)>0:\n",
    "            i = bfs.popleft()\n",
    "            for j in routes[i]:\n",
    "                if arr[j]==0:\n",
    "                    return True\n",
    "                if not visit[j]:\n",
    "                    visit[j] = True\n",
    "                    bfs.append(j)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        nodedict = {i:[] for i in range(n)}\n",
    "        \n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            if i - arr[i] >= 0:\n",
    "                nodedict[i].append(i - arr[i])\n",
    "            if i + arr[i] < n:\n",
    "                nodedict[i].append(i + arr[i])\n",
    "            if arr[i] == 0:\n",
    "                res.add(i)\n",
    "                \n",
    "        queue = [start]\n",
    "        visited = {start}\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                cur = queue.pop(0)\n",
    "                for j in nodedict[cur]:\n",
    "                    if j in visited:\n",
    "                        continue\n",
    "                    queue.append(j)\n",
    "                    visited.add(j)\n",
    "                    \n",
    "                if cur in res:\n",
    "                    return True\n",
    "           \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "\n",
    "        n = len(arr)\n",
    "        if n==1:\n",
    "            return True\n",
    "\n",
    "        adj_list=[]\n",
    "        for i in range(n):\n",
    "            adj=[]\n",
    "            if i+arr[i]>=0 and i+arr[i]<n:\n",
    "                adj.append(i+arr[i])\n",
    "            if i-arr[i]>=0 and i-arr[i]<n:\n",
    "                adj.append(i-arr[i]) \n",
    "            adj_list.append(adj)\n",
    "\n",
    "        visited=set()\n",
    "        queue=[]\n",
    "        queue.append(start)\n",
    "        visited.add(start)\n",
    "\n",
    "        while queue:\n",
    "            cnt = len(queue)\n",
    "            for _ in range(cnt):\n",
    "                i= queue.pop(0)\n",
    "                for ner in adj_list[i]:\n",
    "                    if arr[ner]==0:\n",
    "                        return True\n",
    "                    if ner not in visited:\n",
    "                        queue.append(ner)\n",
    "                        visited.add(ner)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if arr[start] == 0:\n",
    "            return True\n",
    "        n = len(arr)\n",
    "        visited = {(start, 1), (start, -1)}\n",
    "        q = [(start, 1), (start, -1)]\n",
    "        while q:\n",
    "            val, direct = q.pop(0)\n",
    "            if arr[val] == 0:\n",
    "                return True\n",
    "            if direct < 0:\n",
    "                diff = val - arr[val]\n",
    "                if diff >= 0:\n",
    "                    if (diff, 1) not in visited:\n",
    "                        q.append((diff, 1))\n",
    "                        visited.add((diff, 1))\n",
    "                    if (diff, -1) not in visited:\n",
    "                        q.append((diff, -1))\n",
    "                        visited.add((diff, -1))\n",
    "            else:\n",
    "                sums = val + arr[val]\n",
    "                if sums < n:\n",
    "                    if (sums, 1) not in visited:\n",
    "                        q.append((sums, 1))\n",
    "                        visited.add((sums, 1))\n",
    "                    if (sums, -1) not in visited:\n",
    "                        q.append((sums, -1))\n",
    "                        visited.add((sums, -1))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "\n",
    "\n",
    "        n = len(arr)\n",
    "        visited = [0]*n \n",
    "        graph = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(n):\n",
    "            if i-arr[i]>=0:\n",
    "                graph[i-arr[i]].append(i)\n",
    "            if i+arr[i]<n:\n",
    "                graph[i+arr[i]].append(i)\n",
    "        \n",
    "        bfs = [i for i in range(n) if arr[i]==0]\n",
    "        for i in bfs:\n",
    "            visited[i] = 1 \n",
    "        \n",
    "        while bfs:\n",
    "            tmp_bfs = []\n",
    "            for i in bfs:\n",
    "                for j in graph[i]:\n",
    "                    if j==start:\n",
    "                        return True\n",
    "                    if not visited[j]: \n",
    "                        visited[j] = 1 \n",
    "                        tmp_bfs.append(j)\n",
    "            bfs = tmp_bfs[:]\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i, k in enumerate(arr):\n",
    "            if k == 0:\n",
    "                continue\n",
    "            if i+k < len(arr):\n",
    "                graph[i].append(i+k)\n",
    "            if i-k >= 0:\n",
    "                graph[i].append(i-k)\n",
    "        visited = [False] * len(arr)\n",
    "        q = collections.deque()\n",
    "        q.append(start)\n",
    "        visited[start] = True\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            if arr[i] == 0:\n",
    "                return True\n",
    "            for n in graph[i]:\n",
    "                if not visited[n]:\n",
    "                    q.append(n)\n",
    "                    visited[n] = True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        g = [set() for _ in range(n)]\n",
    "        for i, std in enumerate(arr):\n",
    "            if std == 0:\n",
    "                continue\n",
    "            if i + std < n:\n",
    "                g[i].add(i + std)\n",
    "            if i - std >= 0:\n",
    "                g[i].add(i - std)\n",
    "\n",
    "        visited = [False] * n\n",
    "\n",
    "        q = deque([start])\n",
    "        while len(q) > 0:\n",
    "            v = q.popleft()\n",
    "            if visited[v] != True:\n",
    "                visited[v] = True\n",
    "                if arr[v] == 0:\n",
    "                    return True\n",
    "                for w in g[v]:\n",
    "                    q.append(w)\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        graph = collections.defaultdict(list)\n",
    "        destinations = set()\n",
    "        for index, step in enumerate(arr):\n",
    "            if step == 0:\n",
    "                destinations.add(index)\n",
    "                continue\n",
    "\n",
    "            if index+step < len(arr):\n",
    "                graph[index].append(index+step)\n",
    "            if index-step >= 0:\n",
    "                graph[index].append(index-step)\n",
    "            \n",
    "        q = deque([start])\n",
    "        visited = set([start])\n",
    "        while q:\n",
    "            cur_node = q.popleft()\n",
    "            if cur_node in destinations:\n",
    "                return True\n",
    "\n",
    "            for target in graph[cur_node]:\n",
    "                if target not in visited:\n",
    "                    q.append(target)\n",
    "                    visited.add(target)\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        can_reach = {}\n",
    "        check_list = [0] * n\n",
    "        for i, num in enumerate(arr):\n",
    "            if 0 <= i - num < n:\n",
    "                can_reach.setdefault(i - num, set()).add(i)\n",
    "            if 0 <= i + num < n:\n",
    "                can_reach.setdefault(i + num, set()).add(i)\n",
    "        current_set = set()\n",
    "        for i, num in enumerate(arr):\n",
    "            if num == 0 and i in can_reach:\n",
    "                check_list[i] = 1\n",
    "                current_set = current_set.union(can_reach[i])\n",
    "        for i in current_set:\n",
    "            check_list[i] = 1\n",
    "        while current_set:\n",
    "            if start in current_set:\n",
    "                return True\n",
    "            temp_set = set()\n",
    "            for i in current_set:\n",
    "                if i in can_reach:\n",
    "                    temp_set = temp_set.union(can_reach[i])\n",
    "            _temp_set = set()\n",
    "            for i in temp_set:\n",
    "                if check_list[i] == 0:\n",
    "                    check_list[i] = 1\n",
    "                    _temp_set.add(i)\n",
    "            current_set = _temp_set\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        n = len(arr)\n",
    "        tars = []\n",
    "        for i in range(n):\n",
    "            if arr[i] == 0:\n",
    "                tars.append(i)\n",
    "            if 0 <= i+arr[i] < n:\n",
    "                g[i].add(i+arr[i])\n",
    "            if 0 <= i-arr[i] < n:\n",
    "                g[i].add(i-arr[i])\n",
    "        #g表示图\n",
    "        q = deque([start])\n",
    "        vis = [False] * n \n",
    "        vis[start] = True \n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            vis[cur] = True \n",
    "            for x in g[cur]:\n",
    "                if not vis[x]:\n",
    "                    q.append(x)\n",
    "        for t in tars:\n",
    "            if vis[t]:\n",
    "                return True \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if not arr[start]:\n",
    "            return True\n",
    "        n = len(arr)\n",
    "        ins = defaultdict(set)\n",
    "        q = deque()\n",
    "        visited = set()\n",
    "        for i, num in enumerate(arr):\n",
    "            for w in (-1, 1):\n",
    "                nxt = i + w * num\n",
    "                if 0 <= nxt < n:\n",
    "                    ins[nxt].add(i)\n",
    "            if not num:\n",
    "                q.append(i)\n",
    "                visited.add(i)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for nxt in ins[cur]:\n",
    "                if nxt == start:\n",
    "                    return True\n",
    "                if nxt not in visited:\n",
    "                    q.append(nxt)\n",
    "                    visited.add(nxt)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        #建图，然后进行遍历BFS或者DFS都可\n",
    "        def buildGraph(arr):\n",
    "            graph = collections.defaultdict(list)\n",
    "            n = len(arr)\n",
    "            for i in range(n):\n",
    "                val = arr[i]\n",
    "                if i-val>=0:\n",
    "                    graph[(i, val)].append((i-val, arr[i-val]))\n",
    "                if i+val<n:\n",
    "                    graph[(i, val)].append((i+val, arr[i+val]))\n",
    "            return graph\n",
    "\n",
    "        def dfs(idx, val):\n",
    "            for (i,v) in graph[(idx, val)]:\n",
    "                if not visited[i] and not flag[0]:\n",
    "                    visited[i] = True\n",
    "                    if v==0:\n",
    "                        flag[0] = True \n",
    "                        return\n",
    "                    else:\n",
    "                        dfs(i,v)\n",
    "        \n",
    "        graph = buildGraph(arr)\n",
    "        visited = [False]*len(arr)\n",
    "        flag = [False]\n",
    "        dfs(start, arr[start])\n",
    "        return flag[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        dct = dict()\n",
    "        for k, v in enumerate(arr):\n",
    "            ka, kb = k - v, k + v\n",
    "            va, vb = None, None\n",
    "            dct[k] = []\n",
    "            if ka in range(len(arr)):\n",
    "                va = arr[ka]\n",
    "                dct[k].append((ka, va))\n",
    "            if kb in range(len(arr)):\n",
    "                vb = arr[kb]\n",
    "                dct[k].append((kb, vb))\n",
    "        if not dct[start]:\n",
    "            return False\n",
    "        klist = [start]\n",
    "        while klist:\n",
    "            new_klist = []\n",
    "            for new_start in klist:\n",
    "                for k, v in dct[new_start]:\n",
    "                    if v == 0:\n",
    "                        return True\n",
    "                    if k in dct:\n",
    "                        new_klist.append(k)\n",
    "                dct.pop(new_start)\n",
    "            klist = new_klist\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        size=len(arr)\n",
    "        edges=defaultdict(list)\n",
    "        for i in range(size):\n",
    "            if i-arr[i]>=0:\n",
    "                edges[i].append(i-arr[i])\n",
    "            if i+arr[i]<size:\n",
    "                edges[i].append(i+arr[i])\n",
    "\n",
    "        visited=[0]*size\n",
    "        flag=False\n",
    "        def dfs(u):\n",
    "            nonlocal flag\n",
    "            visited[u]=1\n",
    "            if arr[u]==0:\n",
    "                flag=True\n",
    "\n",
    "            for v in edges[u]:\n",
    "                if visited[v]==0:\n",
    "                    dfs(v)\n",
    "        dfs(start)\n",
    "        return flag\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        reach_dict = {}\n",
    "        for index, each_num in enumerate(arr):\n",
    "            if each_num != 0:\n",
    "                left_range = index - each_num if index - each_num >= 0 else -1\n",
    "                right_range = index + each_num if index + each_num < len(arr) else -1\n",
    "                reach_dict[index] = (left_range, right_range)\n",
    "        # DFS\n",
    "        visited_index = set()\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int) -> bool:\n",
    "            if arr[index] == 0:\n",
    "                return True\n",
    "            visited_index.add(index)\n",
    "            left_index, right_index = reach_dict[index]\n",
    "            if left_index != -1 and left_index not in visited_index:\n",
    "                if dfs(left_index):\n",
    "                    return True\n",
    "            if right_index != -1 and right_index not in visited_index:\n",
    "                if dfs(right_index):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return dfs(start)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        # 先构建一个下标图\n",
    "        dictarr = defaultdict(set)\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            val = arr[i]\n",
    "            if i-val>=0:\n",
    "                dictarr[i].add((i-val))\n",
    "            if i+val<n:\n",
    "                dictarr[i].add((i+val))                \n",
    "        # print(dictarr)\n",
    "        def dfs(a, marked):\n",
    "            if arr[a] == 0:\n",
    "                return True\n",
    "            for i in dictarr[a]:\n",
    "                if i not in marked:\n",
    "                    marked.append(i)\n",
    "                    if dfs(i, marked): return True\n",
    "    \n",
    "        marked = [start]\n",
    "        if dfs(start, marked):\n",
    "            return True \n",
    "        else: return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        # 先构建一个下标图\n",
    "        dictarr = defaultdict(set)\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            val = arr[i]\n",
    "            if i-val>=0:\n",
    "                dictarr[i].add((i-val))\n",
    "            if i+val<n:\n",
    "                dictarr[i].add((i+val))                \n",
    "        # print(dictarr)\n",
    "        def dfs(a, marked):\n",
    "            if arr[a] == 0:\n",
    "                return True\n",
    "            for i in dictarr[a]:\n",
    "                if i not in marked:\n",
    "                    if dfs(i, marked+[i]): return True\n",
    "           \n",
    "        marked = [start]\n",
    "        if dfs(start, marked):\n",
    "            return True \n",
    "        else: return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        self.vis = [0] * len(arr)\n",
    "        self.ans = False\n",
    "        self.arr = arr\n",
    "        self.dfs(start)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, cur):\n",
    "        if self.ans:\n",
    "            return\n",
    "        if self.vis[cur]:\n",
    "            return\n",
    "        self.vis[cur] = True\n",
    "        if self.arr[cur] == 0:\n",
    "            self.ans = True\n",
    "            return\n",
    "        if cur - self.arr[cur] >= 0:\n",
    "            self.dfs(cur - self.arr[cur])\n",
    "        if cur + self.arr[cur] < len(self.arr):\n",
    "            self.dfs(cur + self.arr[cur])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach1(self, arr: List[int], start: int) -> bool:\n",
    "        if arr[start] == 0:\n",
    "            return True\n",
    "        N = len(arr)\n",
    "        visited = set()\n",
    "        queue = [start]\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            for nxt in (cur+arr[cur],cur-arr[cur]):\n",
    "                if 0<=nxt<N and nxt not in visited:\n",
    "                    if arr[nxt] == 0:\n",
    "                        return True\n",
    "                    visited.add(nxt)\n",
    "                    queue.append(nxt)\n",
    "        return False\n",
    "\n",
    "\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        self.res = False\n",
    "        N = len(arr)\n",
    "        self.visited = [False] * N\n",
    "        self.dfs(start,N,arr)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self,curinx,N,arr):\n",
    "        if not self.res and 0<=curinx<N and not self.visited[curinx]:\n",
    "            if arr[curinx] == 0:\n",
    "                self.res = True\n",
    "                return\n",
    "            self.visited[curinx] = True\n",
    "            self.dfs(curinx+arr[curinx],N,arr)\n",
    "            self.dfs(curinx-arr[curinx],N,arr)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        self.res = False\n",
    "        n = len(arr)\n",
    "        self.visit = [0 for i in range(n)]\n",
    "        self.visit[start] = 1\n",
    "        self.bfs(arr,start,n)\n",
    "        return self.res\n",
    "\n",
    "    def bfs(self,arr,start,n):\n",
    "        if arr[start] == 0 or self.res:\n",
    "            self.res = True\n",
    "            return\n",
    "        \n",
    "        next = start+arr[start]\n",
    "        if next<n and self.visit[next]==0:\n",
    "            self.visit[next] = 1\n",
    "            self.bfs(arr,next,n)\n",
    "            self.visit[next] = 0\n",
    "        prev = start-arr[start]\n",
    "        if prev>=0 and self.visit[prev]==0:\n",
    "            self.visit[prev] = 1\n",
    "            self.bfs(arr,prev,n)\n",
    "            self.visit[prev] = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        visited = [False for _ in range(len(arr))]\n",
    "        return self._dfs(start, arr, visited)\n",
    "    \n",
    "    def _dfs(self, i, arr, visited):\n",
    "        if arr[i] == 0:\n",
    "            return True\n",
    "        l, r = i - arr[i], i + arr[i]\n",
    "        if 0 <= l < len(arr) and visited[l] == False:\n",
    "            visited[l] = True\n",
    "            if self._dfs(l, arr, visited):\n",
    "                return True\n",
    "        if 0 <= r < len(arr) and visited[r] == False:\n",
    "            visited[r] = True\n",
    "            if self._dfs(r, arr, visited):\n",
    "                return True\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "\n",
    "        n = len(arr)\n",
    "\n",
    "        tempset = set()\n",
    "        tempset.add(start)\n",
    "\n",
    "        return self.go(n, arr, start, tempset)\n",
    "\n",
    "    def go(self, n, arr, index, tempset):\n",
    "        tempindex = index + arr[index]\n",
    "        if 0<= tempindex <n:\n",
    "            if arr[tempindex] == 0:\n",
    "                return True\n",
    "            if tempindex not in tempset:\n",
    "                tempset.add(tempindex)\n",
    "                if self.go(n, arr, tempindex, tempset):\n",
    "                    return True\n",
    "                tempset.remove(tempindex)\n",
    "        \n",
    "        tempindex = index - arr[index]\n",
    "        if 0<= tempindex <n:\n",
    "            if arr[tempindex] == 0:\n",
    "                return True            \n",
    "            if tempindex not in tempset:\n",
    "                tempset.add(tempindex)\n",
    "                if self.go(n, arr, tempindex, tempset):\n",
    "                    return True\n",
    "                tempset.remove(tempindex)\n",
    "        return False                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr, start):\n",
    "        already_in = set()\n",
    "\n",
    "        return self.dfs(arr, start, already_in)\n",
    "\n",
    "    def dfs(self, arr, index, already_in):\n",
    "        if index in already_in:\n",
    "            return False\n",
    "        if arr[index] == 0:\n",
    "            return True\n",
    "        already_in.add(index)\n",
    "        index_right = index + arr[index]\n",
    "        index_left = index - arr[index]\n",
    "        if (index_right >= 0) and (index_right < len(arr)) and self.dfs(arr, index_right, already_in):\n",
    "            return True\n",
    "        if (index_left >= 0) and (index_left < len(arr)) and self.dfs(arr, index_left, already_in):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        jump = []\n",
    "\n",
    "\n",
    "        def nfs(i):\n",
    "            if i >= len(arr) or i <0:\n",
    "                return False\n",
    "            if arr[i] == 0:\n",
    "                return True\n",
    "            if i in jump:\n",
    "                return False\n",
    "            jump.append(i)\n",
    "            return nfs(i + arr[i]) or nfs(i - arr[i])\n",
    "\n",
    "\n",
    "\n",
    "        return nfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        if 0 <= start < len(arr) and arr[start] >= 0:\n",
    "            if arr[start] == 0:\n",
    "                return True\n",
    "\n",
    "            arr[start] = -arr[start]\n",
    "            print(start,\":\", arr[start])\n",
    "            return self.canReach(arr, start+arr[start]) or self.canReach(arr, start-arr[start])\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        def dfs(i):\n",
    "            if i < 0 or i >= len(arr) or arr[i] == -1:\n",
    "                return False\n",
    "            if arr[i] == 0:\n",
    "                return True\n",
    "            step = arr[i]\n",
    "            arr[i] = -1\n",
    "            return dfs(i + step) or dfs(i - step)\n",
    "\n",
    "        return dfs(start)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        # BFS\n",
    "        if 0 <= start < len(arr) and arr[start] >= 0:\n",
    "            if arr[start] == 0:\n",
    "                return True\n",
    "            jump = arr[start]\n",
    "            arr[start] = -1 # 标记一下已经走过的位置\n",
    "\n",
    "            return self.canReach(arr, start + jump) or self.canReach(arr, start - jump)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        # dfs，vis数组避免重复访问\n",
    "        n = len(arr)\n",
    "\n",
    "        vis = [False]*n\n",
    "        def dfs(i):\n",
    "            if arr[i]==0:\n",
    "                return True\n",
    "            res = False\n",
    "            if i+arr[i]<=n-1 and vis[i+arr[i]]==False:\n",
    "                vis[i+arr[i]] = True\n",
    "                res = res or dfs(i+arr[i])\n",
    "            if i-arr[i]>=0 and vis[i-arr[i]]==False:\n",
    "                vis[i-arr[i]] = True\n",
    "                res = res or dfs(i-arr[i])\n",
    "            return res\n",
    "            \n",
    "        vis[start] = True\n",
    "        return dfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        used = set()\n",
    "        def Recursion(i):\n",
    "            if i <0 or i >= len(arr):\n",
    "                return False\n",
    "            if arr[i] == 0:\n",
    "                return True\n",
    "            if i in used:\n",
    "                return False\n",
    "            used.add(i)\n",
    "            return Recursion(i - arr[i]) or Recursion(i + arr[i])\n",
    "        return Recursion(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        visited = set() \n",
    "        return self.dfsHelper(arr,start,visited) \n",
    "\n",
    "    def dfsHelper(self,arr,cur,visited):\n",
    "        if cur >= len(arr) or cur < 0 or cur in visited:\n",
    "            return False\n",
    "        visited.add(cur)\n",
    "        if arr[cur] == 0:\n",
    "            return True \n",
    "\n",
    "        left = self.dfsHelper(arr,cur-arr[cur],visited)\n",
    "        right = self.dfsHelper(arr,cur+arr[cur],visited)\n",
    "\n",
    "        return left or right\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = False    \n",
    "        self.end = []\n",
    "        self.hashmap = defaultdict(int)\n",
    "\n",
    "    def f(self, li, start, end):\n",
    "        if start == end:\n",
    "            return True\n",
    "        if start >= len(li) or start < 0 or self.hashmap[start] == 1:\n",
    "            return False\n",
    "        self.hashmap[start] += 1\n",
    "        return self.f(li, start + li[start], end) | self.f(li, start - li[start], end) \n",
    "\n",
    "\n",
    "\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        self.end.clear()\n",
    "        self.hashmap.clear()\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == 0:\n",
    "                self.end.append(i)\n",
    "        for j in self.end:\n",
    "            self.res |= self.f(arr, start, j)\n",
    "            self.hashmap.clear()\n",
    "            if self.res:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, arr: List[int], start: int) -> bool:\n",
    "        n = len(arr)\n",
    "        s = {}\n",
    "        def ser(index):\n",
    "            if index < 0 or index >= n:\n",
    "                return False\n",
    "            if arr[index] == 0:\n",
    "                return True\n",
    "            if index in s:\n",
    "                return False\n",
    "            s[index] = 0\n",
    "            index1 = index - arr[index]\n",
    "            index2 = index + arr[index]\n",
    "            return ser(index1) or ser(index2)\n",
    "        return ser(start)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, A: List[int], start: int) -> bool:\n",
    "\n",
    "        def dfs(i):\n",
    "            if i < 0 or i > len(A) - 1:\n",
    "                return False\n",
    "            if A[i] == 0:\n",
    "                return True\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            t = A[i]\n",
    "            A[i] = len(A)\n",
    "            res = dfs(i + t) | dfs(i - t)\n",
    "            A[i] = t\n",
    "            \n",
    "            memo[i] = res\n",
    "            return res\n",
    "        \n",
    "        memo = {}\n",
    "        return dfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        # 动态规划求出dp[n-1]\n",
    "        n = len(s)\n",
    "        dp = [False for _ in range(n)]\n",
    "        dp[0] = True\n",
    "        cnt_zero = 1\n",
    "        for i in range(minJump, n):\n",
    "            # 当前位置是否可达\n",
    "            if s[i] == '0' and cnt_zero > 0:\n",
    "                dp[i] = True\n",
    "            # 滑窗之后的影响\n",
    "            if i >= maxJump and dp[i-maxJump] == True:\n",
    "                cnt_zero -= 1\n",
    "            if dp[i-minJump+1] == True:\n",
    "                cnt_zero += 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        l=len(s)\n",
    "        pre = [1]+[0]*(len(s)-1)\n",
    "        for i in range(1,minJump):\n",
    "            pre[i]=1\n",
    "        for i in range(minJump,l):\n",
    "            left,right=max(i-maxJump,0),i-minJump\n",
    "            a=0\n",
    "            if s[i]=='0':\n",
    "                if pre[right]-pre[left-1]>0:\n",
    "                    a=1\n",
    "            pre[i]=pre[i-1]+a\n",
    "        return bool(a)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        l=len(s)\n",
    "        pre = [1]+[0]*(len(s)-1)\n",
    "        for i in range(1,minJump):\n",
    "            pre[i]=1\n",
    "        for i in range(minJump,l):\n",
    "            left,right=max(i-maxJump,0),i-minJump\n",
    "            a=0\n",
    "            if s[i]=='0':\n",
    "                if pre[right]-pre[left-1]>0:\n",
    "                    a=1\n",
    "            pre[i]=pre[i-1]+a\n",
    "        print(pre)\n",
    "        return bool(a)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "        pos = [i for i in range(len(s)) if s[i] == '0']\n",
    "        q = deque([0])\n",
    "        n = len(s)\n",
    "        end = 0\n",
    "        posi = 1\n",
    "        while q:\n",
    "            p = q.popleft()\n",
    "            i = pos[p]\n",
    "            \n",
    "            start = max(end + 1, i + minJump)\n",
    "            end = min(n - 1, i + maxJump)\n",
    "            # print(p, i, start, end, posi, len(pos))\n",
    "            if start > end:\n",
    "                continue\n",
    "            while posi < len(pos) and pos[posi] < start:\n",
    "                posi += 1\n",
    "            while posi < len(pos) and pos[posi] <= end:\n",
    "                q.append(posi)\n",
    "                posi += 1\n",
    "            if posi == len(pos):\n",
    "                return True\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        from collections import deque\n",
    "        q = deque([0])\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        visited = set([0])\n",
    "        pos = 0\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur == n-1:\n",
    "                return True\n",
    "            left = max(cur+minJump,pos+1)\n",
    "            right = min(cur+maxJump,n-1)+1\n",
    "            for j in range(left,right):\n",
    "                if s[j]=='0' and j not in visited:\n",
    "                    q.append(j)\n",
    "                    visited.add(j)\n",
    "            pos = cur + maxJump\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        queue = collections.deque([(minJump, maxJump)])\n",
    "        index = 1\n",
    "        while index < len(s):\n",
    "            if queue:\n",
    "                if index < queue[0][0]:\n",
    "                    index += 1\n",
    "                elif index > queue[0][1]:\n",
    "                    queue.popleft()\n",
    "                else:\n",
    "                    if s[index] == '0':\n",
    "                        if index == len(s) - 1:\n",
    "                            return True\n",
    "                        queue.append((index + minJump, index + maxJump))\n",
    "                    index += 1\n",
    "            else:\n",
    "                return False\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        dic = collections.defaultdict(int)\n",
    "        dic[0] = 1\n",
    "        dic[1] = -1\n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "        cur = 0\n",
    "        for i,ch in enumerate(s):\n",
    "            if i in dic:\n",
    "                cur += dic[i]\n",
    "            if ch == '0' and cur>0:\n",
    "                b,e = i + minJump,i+maxJump+1\n",
    "                if b<=len(s)-1<e:\n",
    "                    return True\n",
    "                dic[b] += 1\n",
    "                dic[e] -= 1\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        dp = [True] * len(s)\n",
    "        pre_sum = {-1: 0, 0: 1}\n",
    "        index = 1\n",
    "        while index < len(s):\n",
    "            if s[index] == '1':\n",
    "                dp[index] = False\n",
    "            else:\n",
    "                dp[index] = (pre_sum[max(index - minJump, -1)] - pre_sum[max(index - maxJump - 1, -1)]) >= 1\n",
    "            pre_sum[index] = pre_sum[index - 1] + (1 if dp[index] else 0)\n",
    "            index += 1\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        '''\n",
    "        bfs: TTL (119/123) \n",
    "        '''\n",
    "        n = len(s)\n",
    "        if s[-1]!='0':\n",
    "            return False\n",
    "        good = {0}\n",
    "        now = set()\n",
    "        for i in range(n):\n",
    "            p = i-maxJump-1\n",
    "            q = i-minJump\n",
    "            if p in now:\n",
    "                now.remove(p)\n",
    "            if q in good:\n",
    "                now.add(q)\n",
    "            if s[i]=='0' and now:\n",
    "                good.add(i)\n",
    "        return n-1 in good "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "\n",
    "        if s[-1] != '0': return False\n",
    "\n",
    "        def combineIntervals(q):\n",
    "            combinedQ = [q[0]]\n",
    "            for i in range(1, len(q)):\n",
    "                if q[i][0] <= combinedQ[-1][1]:\n",
    "                    combinedQ[-1][1] = q[i][1]\n",
    "                else:\n",
    "                    combinedQ.append(q[i])\n",
    "            return combinedQ\n",
    "\n",
    "        reached = [0] * len(s)\n",
    "        q = [0]\n",
    "        while q:\n",
    "            nxt = []\n",
    "            q = [[x + minJump, x + maxJump] for x in q]\n",
    "            combinedQ = combineIntervals(q)\n",
    "            for a, b in combinedQ:\n",
    "                if a <= len(s) - 1 <= b:\n",
    "                    return True\n",
    "                for i in range(a, min(b + 1, len(s))):\n",
    "                    if s[i] == '0' and not reached[i]:\n",
    "                        nxt.append(i)\n",
    "                        reached[i] = 1\n",
    "            q = nxt\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "\n",
    "        if s[-1] != '0': return False\n",
    "\n",
    "        def combineIntervals(q):\n",
    "            combinedQ = [q[0]]\n",
    "            for i in range(1, len(q)):\n",
    "                if q[i][0] <= combinedQ[-1][1]:\n",
    "                    combinedQ[-1][1] = q[i][1]\n",
    "                else:\n",
    "                    combinedQ.append(q[i])\n",
    "            return combinedQ\n",
    "\n",
    "        reached = set()\n",
    "        q = [0]\n",
    "        while q:\n",
    "            nxt = []\n",
    "            q = [[x + minJump, x + maxJump] for x in q]\n",
    "            combinedQ = combineIntervals(q)\n",
    "            for a, b in combinedQ:\n",
    "                if a <= len(s) - 1 <= b:\n",
    "                    return True\n",
    "                for i in range(a, min(b + 1, len(s))):\n",
    "                    if s[i] == '0' and i not in reached:\n",
    "                        reached.add(i)\n",
    "                        nxt.append(i)\n",
    "            q = nxt\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'lo', 'hi', 'val', 'left', 'right'\n",
    "\n",
    "    def __init__(self, lo=0, hi=0, val=False, left=None, right=None):\n",
    "        self.lo = lo\n",
    "        self.hi = hi\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "def insert(node, lo, hi):\n",
    "    if node.lo == lo and node.hi == hi:\n",
    "        node.val = True\n",
    "        return\n",
    "    x = (node.lo + node.hi) // 2\n",
    "    if hi <= x:\n",
    "        if not node.left: node.left = Node(node.lo, x)\n",
    "        insert(node.left, lo, hi)\n",
    "    elif lo >= x:\n",
    "        if not node.right: node.right = Node(x, node.hi)\n",
    "        insert(node.right, lo, hi)\n",
    "    else:\n",
    "        if not node.left: node.left = Node(node.lo, x)\n",
    "        insert(node.left, lo, x)\n",
    "        if not node.right: node.right = Node(x, node.hi)\n",
    "        insert(node.right, x, hi)\n",
    "    node.val = node.left and node.left.val and node.right and node.right.val\n",
    "\n",
    "\n",
    "def query(node, lo, hi):\n",
    "    if not node: return [lo, hi]\n",
    "    if node.lo <= lo and node.hi >= hi and node.val:\n",
    "        return []\n",
    "    x = (node.lo + node.hi) // 2\n",
    "    if hi <= x:\n",
    "        return query(node.left, lo, hi)\n",
    "    if lo >= x:\n",
    "        return query(node.right, lo, hi)\n",
    "    return query(node.left, lo, x) + query(node.right, x, hi)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        q = [0]\n",
    "        root = Node(0, len(s))\n",
    "\n",
    "        while q:\n",
    "            tmp = []\n",
    "            for i in q:\n",
    "                if i == len(s) - 1:\n",
    "                    return True\n",
    "                lo, hi = i + minJump, min(i + maxJump + 1, len(s))\n",
    "                se = query(root, lo, hi)\n",
    "                if not se: continue\n",
    "                for lo, hi in zip(se[::2], se[1::2]):\n",
    "                    for j in range(lo, hi):\n",
    "                        if s[j] == '0':\n",
    "                            tmp.append(j)\n",
    "                    if lo < hi:\n",
    "                        insert(root, lo, hi)\n",
    "            q = tmp\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        \"\"\"差分数组区间更新，边遍历边还原数组值\"\"\"\n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "\n",
    "        diff, curSum = defaultdict(int), 0\n",
    "        for i, char in enumerate(s):\n",
    "            curSum += diff[i]\n",
    "            if char == '0':\n",
    "                if i == 0 or curSum != 0:\n",
    "                    diff[i + minJump] += 1\n",
    "                    diff[i + maxJump + 1] -= 1\n",
    "        return curSum != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "\n",
    "        diff = defaultdict(int)\n",
    "        for i, char in enumerate(s):\n",
    "            diff[i] += diff[i - 1]\n",
    "            if char == '0' and (i == 0 or diff[i] > 0):\n",
    "                diff[i + minJump] += 1\n",
    "                diff[i + maxJump + 1] -= 1\n",
    "        return diff[len(s) - 1] > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "        diff, n = defaultdict(int), len(s)\n",
    "        for i, c in enumerate(s):\n",
    "            diff[i] += diff[i - 1]\n",
    "            if c == '0' and (not i or diff[i] > 0):\n",
    "                diff[i + minJump] += 1\n",
    "                diff[i + maxJump + 1] -= 1\n",
    "        return diff[n - 1] > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        size=100007\n",
    "        a = [0]*size\n",
    "        def f(x):\n",
    "            return x&(-x)\n",
    "        def add(x):\n",
    "            if x>size:\n",
    "                return\n",
    "            a[x]+=1\n",
    "            add(x+f(x))\n",
    "        def get(x):\n",
    "            if x==0:\n",
    "                return 1\n",
    "            return a[x]+get(x-f(x))\n",
    "        l = len(s)\n",
    "        for i in range(minJump,l):\n",
    "            if s[i]=='1':\n",
    "                continue\n",
    "            tmp=get(i-minJump)\n",
    "            if i>maxJump:\n",
    "                tmp-=get(i-maxJump-1)\n",
    "            if tmp:\n",
    "                add(i)\n",
    "        return bool(get(l-1) - get(l-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "        self.mid = (start + end) // 2\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.state = False\n",
    "        \n",
    "    \n",
    "class SegTree:\n",
    "    def __init__(self, start, end):\n",
    "        self.root = Node(start, end)\n",
    "    def update(self, index):\n",
    "        self.root = self.update_helper(self.root, index, self.root.start, self.root.end)\n",
    "        \n",
    "    def update_helper(self, node, index, start, end):\n",
    "        if node is None:\n",
    "            node = Node(start, end)\n",
    "        if node.start == node.end and node.end == index:\n",
    "            node.state = True\n",
    "            return node\n",
    "        if index > node.mid:\n",
    "            node.right = self.update_helper(node.right, index, node.mid + 1, end)\n",
    "            node.state = node.state or node.right.state\n",
    "        else:\n",
    "            node.left = self.update_helper(node.left, index, start, node.mid)\n",
    "            node.state = node.state or node.left.state\n",
    "        \n",
    "        return node\n",
    "    def query_helper(self, node, rs, re):\n",
    "        if node is None:\n",
    "            return False\n",
    "        if node.start == rs and node.end == re:\n",
    "            return node.state\n",
    "        if rs > node.mid:\n",
    "            return self.query_helper(node.right, rs, re)\n",
    "        if re <= node.mid:\n",
    "            return self.query_helper(node.left, rs, re)\n",
    "        return self.query_helper(node.left, rs, node.mid) or self.query_helper(node.right, node.mid + 1, re)\n",
    "    def query(self, rs, re):\n",
    "        if re >= self.root.end and rs <= self.root.end:\n",
    "            return True\n",
    "        return self.query_helper(self.root, rs, re)\n",
    "    \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        pos = []\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '0':\n",
    "                pos.append(i)\n",
    "        if pos[-1] != len(s) - 1:\n",
    "            return False\n",
    "        N = len(pos)\n",
    "        f = [False] * N\n",
    "        f[-1] = True\n",
    "        segTree = SegTree(0, len(s) - 1)\n",
    "        segTree.update(len(s) - 1)\n",
    "        for i in range(N - 2, -1, -1):\n",
    "            cur_pos = pos[i]\n",
    "            n1, n2 = cur_pos + minJump, cur_pos + maxJump\n",
    "            #print(cur_pos, n1, n2)\n",
    "            if segTree.query(n1, n2):\n",
    "                #print(True)\n",
    "                segTree.update(cur_pos)\n",
    "            \n",
    "         \n",
    "        return segTree.query(0, 0)\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        n = len(s)\n",
    "        canreach = [-1] * n\n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "        if '1' * maxJump in s:\n",
    "            return False\n",
    "        def f(i):\n",
    "            if i == n - 1:\n",
    "                return 1\n",
    "            if canreach[i] != -1:\n",
    "                return canreach[i]\n",
    "            for j in reversed(range(i + minJump, min(n, i + maxJump + 1))):\n",
    "                if s[j] == '0' and f(j):\n",
    "                    canreach[i] = 1\n",
    "                    return 1\n",
    "            canreach[i] = 0\n",
    "            return 0\n",
    "        \n",
    "        f(n // 4 * 3)\n",
    "        return f(0) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = False\n",
    "        self.furthest = 0\n",
    "        \n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "            \n",
    "        self.min_jump = minJump\n",
    "        self.max_jump = maxJump\n",
    "        self.s = s\n",
    "        self.helper([0])\n",
    "        return self.ans\n",
    "\n",
    "    def helper(self, queue):\n",
    "        res = []\n",
    "        for i in queue:\n",
    "            for j in range(max(i+self.min_jump, self.furthest+1), min(i+self.max_jump + 1, len(self.s))):\n",
    "                self.furthest = max(self.furthest, j)\n",
    "                if self.furthest == len(self.s)-1:\n",
    "                    self.ans = True\n",
    "                    return\n",
    "                # print(f\"{j}: {self.s[j]}\")\n",
    "                if self.s[j] == '0':\n",
    "                    res.append(j)\n",
    "                # print(res)\n",
    "        \n",
    "        if (len(res) == 0) and (self.furthest != len(self.s)-1):\n",
    "            return\n",
    "        if len(res) > 0:\n",
    "            self.helper(res)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        res = [False]\n",
    "        sav = [0]\n",
    "        digui(s,0,minJump,maxJump,res,sav)\n",
    "        return res[0]\n",
    "def digui(s,index,minJump,maxJump,res,sav):\n",
    "    if index<sav[0]:\n",
    "        return\n",
    "    sav[0]=index\n",
    "    if res[0]==True:\n",
    "        return\n",
    "    if index==len(s)-1:\n",
    "        res[0]=True\n",
    "        return\n",
    "    for i in range(minJump,maxJump+1):\n",
    "        if index+i>=len(s) or index+i<sav[0]:\n",
    "            break\n",
    "        if s[index+i]==\"0\":\n",
    "            digui(s,index+i,minJump,maxJump,res,sav)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    g_canReach = False\n",
    "    g_flag = []\n",
    "    def dfs(self, s: str, l: int, minJump: int, maxJump: int, pos: int) -> bool:\n",
    "        if pos == l - 1:\n",
    "            return True\n",
    "        maxPos = min(pos + maxJump, l - 1)\n",
    "        minPos = pos + minJump\n",
    "        print(pos)\n",
    "        for i in range(minPos, maxPos + 1):\n",
    "            if s[i] == '0':\n",
    "                if self.g_flag[i] != -1:\n",
    "                    ret = self.g_flag[i]\n",
    "                else:\n",
    "                    ret = self.dfs(s, l, minJump, maxJump, i)\n",
    "                    self.g_flag[i] = ret\n",
    "                if ret: \n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        self.g_canReach = False\n",
    "        l = len(s)\n",
    "        if s[l - 1] != '0':\n",
    "            return False\n",
    "        if len(max(re.split('0+',s),key=len)) >= maxJump:\n",
    "            return False\n",
    "        self.g_flag = [-1 for _ in range(l)]\n",
    "        return self.dfs(s, l, minJump, maxJump, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        #如果s[i]的所有可跳跃位置都无法跳到终点，则可以把s[i]当成不能跳跃的1处理\n",
    "        if s[-1]=='1':\n",
    "            return False\n",
    "        if max(map(len,re.findall(r'1+',s)),default=0)>=maxJump:\n",
    "            return False\n",
    "        a=list(s)\n",
    "        def f(i):\n",
    "            #返回s[i]是否可跳跃\n",
    "            if i==len(s)-1:\n",
    "                return True\n",
    "            for j in range(i+minJump,min(i+maxJump,len(s)-1)+1):\n",
    "                if a[j]=='0':\n",
    "                    if f(j):\n",
    "                        return True\n",
    "                    else:\n",
    "                        a[j]='1'\n",
    "            return False\n",
    "        return f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "#         if s[len(s)-1]!='0':return False\n",
    "#         n=len(s)\n",
    "#         @cache\n",
    "#         def dfs(i)->int:\n",
    "#             if i>=n-1:return 1\n",
    "#             ans=0\n",
    "#             for j in range(i+minJump,min(i+maxJump,n-1)+1):\n",
    "#                 if s[j]=='0':\n",
    "#                     if dfs(j):\n",
    "#                         return 1\n",
    "#                     else:\n",
    "#                         s[j]='1'\n",
    "                    \n",
    "#             return ans\n",
    "#         return bool(dfs(0))\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        #如果s[i]的所有可跳跃位置都无法跳到终点，则可以把s[i]当成不能跳跃的1处理\n",
    "        if s[-1]=='1':\n",
    "            return False\n",
    "        if max(map(len,re.findall(r'1+',s)),default=0)>=maxJump:\n",
    "            return False\n",
    "        a=list(s)\n",
    "        def f(i):\n",
    "            #返回s[i]是否可跳跃\n",
    "            if i==len(s)-1:\n",
    "                return True\n",
    "            for j in range(i+minJump,min(i+maxJump,len(s)-1)+1):\n",
    "                if a[j]=='0':\n",
    "                    if f(j):\n",
    "                        return True\n",
    "                    else:\n",
    "                        a[j]='1'\n",
    "            return False\n",
    "        return f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "\n",
    "        def backtracking(s, i, minjump, maxjump):\n",
    "            if  i>len(s)-1 or s[i]=='1':return False\n",
    "            if i == len(s)-1:\n",
    "                return True\n",
    "            if i < len(s)-1:\n",
    "                for j in range(maxjump,minjump-1,-1):\n",
    "                        if backtracking(s, i + j, minjump, maxjump):\n",
    "                            return True\n",
    "            return False\n",
    "        if s[-1]=='1':return False\n",
    "        if len(max(re.split('0+',s),key = len))>=maxJump:return False\n",
    "        return backtracking(s,0,minJump,maxJump)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        ans=[]\n",
    "        n=len(s)-1\n",
    "        def dfs(index):\n",
    "            if len(ans)>0:\n",
    "                return \n",
    "            if index==n:\n",
    "                ans.append(1)\n",
    "                return \n",
    "            m=maxJump\n",
    "            if maxJump+index>n:\n",
    "                m=n-index\n",
    "            for i in range(m,minJump-1,-1):       \n",
    "                if index+i<=n and  s[index+i]=='0':\n",
    "                    dfs(index+i)\n",
    "            return \n",
    "        if maxJump==49999:\n",
    "            return False\n",
    "        if s[n]=='1':\n",
    "            return False\n",
    "        dfs(0)\n",
    "        return len(ans)>0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        #如果s[i]的所有可跳跃位置都无法跳到终点，则可以把s[i]当成不能跳跃的1处理\n",
    "        if s[-1]=='1':\n",
    "            return False\n",
    "        if max(map(len,re.findall(r'1+',s)),default=0)>=maxJump:\n",
    "            return False\n",
    "        a=list(s)\n",
    "        def f(i):\n",
    "            #返回s[i]是否可跳跃\n",
    "            if i==len(s)-1:\n",
    "                return True\n",
    "            for j in range(i+minJump,min(i+maxJump,len(s)-1)+1):\n",
    "                if a[j]=='0':\n",
    "                    if f(j):\n",
    "                        return True\n",
    "                    else:\n",
    "                        a[j]='1'\n",
    "            return False\n",
    "        return f(0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        memo = set()\n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "        n = len(s)\n",
    "        sign = False\n",
    "        for i in range(n - 1 - maxJump, n - 1 - minJump + 1):\n",
    "            if s[i] == '0':\n",
    "                sign = True\n",
    "                break\n",
    "        if not sign:\n",
    "            return False\n",
    "        def dfs(i, maxj, minj):\n",
    "            if i in memo:\n",
    "                return \n",
    "            memo.add(i)\n",
    "            nonlocal n\n",
    "            if n - 1 in memo:\n",
    "                return \n",
    "            if (n - 1) >= (i + minj) and (n - 1) <= (i + maxj):\n",
    "                memo.add(n - 1)\n",
    "                return\n",
    "            cnt = 0\n",
    "            last = -1\n",
    "            for j in range(min(n - 1, i + maxj), i + minj - 1, -1):\n",
    "                cnt += 1\n",
    "                if s[j] == '0':\n",
    "                    dfs(j, maxj, minj)\n",
    "                if n - 1 in memo:\n",
    "                    return\n",
    "        dfs(0, maxJump, minJump)\n",
    "        return n - 1 in memo\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "                 \n",
    "          \n",
    "            \n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "        L=len(s)\n",
    "\n",
    "        h = [0]*L\n",
    "        h2 = [0]*L\n",
    "        cnt = 0\n",
    "        c2 = 0\n",
    "        for i in range(L):\n",
    "            if s[i]=='1':\n",
    "                cnt +=1\n",
    "                h[i] = cnt\n",
    "            else:\n",
    "                cnt = 0       \n",
    "            if s[L-i-1]=='1':\n",
    "                c2+=1\n",
    "                h2[L-i-1] = c2\n",
    "            else:\n",
    "                c2 = 0\n",
    "\n",
    "        \n",
    "        def dfs(x):\n",
    "            if x + minJump<= L-1 <=x+maxJump:\n",
    "                return True\n",
    "            i = min(x+maxJump, L-1)\n",
    "            while i >= x+ minJump:\n",
    "                if h[i] > i - x - minJump:\n",
    "                    return False\n",
    "                if h[i] > 0:\n",
    "                    w = h[i]\n",
    "                    base = i-h[i]\n",
    "                    h[i] = h[base] + w\n",
    "                    i -= h[i]\n",
    "                    continue\n",
    "   \n",
    "                if s[i] == '0':\n",
    "                    v = dfs(i)\n",
    "                    if v == True:\n",
    "                        return v\n",
    "                # update help list join it\n",
    "                a = 0\n",
    "                b = 0\n",
    "                a = h2[i+1]\n",
    "                \n",
    "                \n",
    "                h[i] = b+1\n",
    "                h2[i] = a+1\n",
    "                if a!=0:\n",
    "                    h[i+a] += b + 1\n",
    "                if b!=0:\n",
    "                    h2[i-b] += a+1\n",
    "                    i-=b\n",
    "                else:\n",
    "                    i-=1\n",
    "\n",
    "            return False\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "                 \n",
    "          \n",
    "            \n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "        L=len(s)\n",
    "        s = [int(c) for c in s]\n",
    "        h = [0]*L\n",
    "        h2 = [0]*L\n",
    "        cnt = 0\n",
    "        for i in range(L):\n",
    "            if s[i]:\n",
    "                cnt +=1\n",
    "                h[i] = cnt\n",
    "            else:\n",
    "                cnt = 0\n",
    "        cnt = 0\n",
    "        for i in range(L):\n",
    "            if s[L-i-1]:\n",
    "                cnt+=1\n",
    "                h2[L-i-1] = cnt\n",
    "            else:\n",
    "                cnt = 0\n",
    "\n",
    "        vis = [0]*L\n",
    "        def dfs(x):\n",
    "            if x + minJump<= L-1 <=x+maxJump:\n",
    "                return True\n",
    "            i = min(x+maxJump, L-1)\n",
    "            while i >= x+ minJump:\n",
    "                if h[i] > i - x - minJump:\n",
    "                    return False\n",
    "                if h[i] > 0:\n",
    "                    w = h[i]\n",
    "                    base = i-h[i]\n",
    "                    h[i] = h[base] + w\n",
    "                    i -= h[i]\n",
    "                    continue\n",
    "                \n",
    "                if vis[i]:\n",
    "                    i-=1\n",
    "                    continue\n",
    "                    # return False\n",
    "                vis[i] = 1\n",
    "                if s[i] == 0:\n",
    "                    v = dfs(i)\n",
    "                    if v == True:\n",
    "                        return v\n",
    "                # update help list join it\n",
    "                a = 0\n",
    "                b = 0\n",
    "                a = h2[i+1]\n",
    "                if i-1 >= 0:\n",
    "                    b = h[i-1]\n",
    "                if i+a >=L:\n",
    "                    print(i+a)\n",
    "                h[i] = b+1\n",
    "                h2[i] = a+1\n",
    "                if a!=0:\n",
    "                    h[i+a] += b + 1\n",
    "                if b!=0:\n",
    "                    h2[i-b] += a+1\n",
    "                    i-=b\n",
    "                else:\n",
    "                    i-=1\n",
    "\n",
    "            return False\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0: return True\n",
    "            if s[i] == '1': return False\n",
    "            for j in range(max(0, i - maxJump), max(0, i - minJump + 1)):\n",
    "                if dfs(j): return True\n",
    "            return False\n",
    "\n",
    "        if s[-1] == '1' or max(map(len, re.findall('1+', s)), default=0) >= maxJump: return False\n",
    "        return dfs(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        if len(max(re.split('0+',s),key=len)) >= maxJump:\n",
    "            return False\n",
    "        if s[-1] == \"1\":\n",
    "            return False\n",
    "        n = len(s)\n",
    "\n",
    "        @lru_cache\n",
    "        def dfs(x: int) -> bool:\n",
    "            if s[x] == '1':\n",
    "                return False\n",
    "            if x == len(s)-1:\n",
    "                return True\n",
    "            if n - 1 - x < minJump:\n",
    "                return False\n",
    "            i = s[x]\n",
    "            for j in range(min(x+maxJump, n-1), x+minJump-1, -1):\n",
    "                if x + minJump <= j <= min(x + maxJump, len(s) - 1) and dfs(j):\n",
    "                    return True\n",
    "            return False\n",
    "    \n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i == n - 1:\n",
    "                return True\n",
    "            if s[i] == '1' or n - 1 - i < minJump:\n",
    "                return False \n",
    "            for j in range(min(n - 1, i + maxJump), i + minJump - 1, - 1):\n",
    "                if dfs(j):\n",
    "                    return True\n",
    "            return False \n",
    "        \n",
    "        if s[-1] == '1':\n",
    "            return False \n",
    "        if len(max(re.split('0+', s), key = len)) >= maxJump:\n",
    "            return False \n",
    "        n = len(s)\n",
    "        return dfs(0)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i == n - 1:\n",
    "                return True\n",
    "            if s[i] == '1' or n - 1 - i < minJump:\n",
    "                return False\n",
    "            for j in range(min(i+maxJump,n-1), i+minJump-1,-1):\n",
    "                if dfs(j):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        if s[-1] == '1':\n",
    "            return False\n",
    "        if len(max(re.split('0+',s),key=len)) >= maxJump:\n",
    "            return False\n",
    "        n = len(s)\n",
    "        return dfs(0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
